package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/8/12 23:12
 */
public class DungeonGame_174 {

    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0) return 1;
        int width = dungeon[0].length, height = dungeon.length;
        // 0 -- 表示当前血量； 1 -- 表示补充的血量
        final int[][] dp = new int[height][width];
        // 反向DP
        // 注意判断方程的“后向有效性”
        for (int i = height - 1; i >= 0; i--) {
            for (int j = width - 1; j >= 0; j--) {
                if (i == height - 1 && j == width - 1) {
                    dp[i][j] = 1 - dungeon[i][j];
                } else if (i == height - 1 && j < width - 1) {
                    dp[i][j] = dp[i][j + 1] - dungeon[i][j];
                } else if (j == width - 1 && i < height - 1) {
                    dp[i][j] = dp[i][j + 1] - dungeon[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                }
                if (dp[i][j] <= 0) dp[i][j] = 1;
            }
        }
        return dp[0][0];
    }

}
